package com.jlh.viewer.algorithm;

import java.util.Arrays;

/**
 * Created by jlh
 * On 2017/3/14 0014.
 */
public class MergeSort {
    public static void main(String[] args) {
        int b[]={4,5,1,2,3,8,11,6,7,10};
        MergeSort mergeSort= new MergeSort();
        mergeSort.sort(b,0,b.length);
        Arrays.stream(b).forEach(System.out::println);
    }

    public void sort (int a[],int first,int last){
        reslove(a,first,last-1,new int[a.length]);
    }

    private void reslove(int a[], int first, int last, int[] temp){
        if (first<last){
            int mid = (first+last)/2;
            //以后处理边界问题，统一从0到length-1 然后用包涵等于处理，0到length 不包含等于处理的时候逻辑很容易混乱
            reslove(a,first,mid,temp);
            reslove(a,mid+1,last,temp);
            merge(a,first,mid,last,temp);
        }
    }

    private void merge(int a[], int first, int mid, int last, int[] temp){
        int i=first,j=mid+1,k=0;
        while (i<=mid&&j<=last){
            if (a[i]<=a[j])
                temp[k++]=a[i++];
            else
                temp[k++]=a[j++];
        }
        while (i <= mid)
            temp[k++] = a[i++];

        while (j <= last)
            temp[k++] = a[j++];
        for (i=0;i<k;i++){
            a[first+i]=temp[i];
        }
    }

}
